/*
 * LinkedList.cpp
 *
 *  Created on: Jul 7, 2012
 *      Author: jh238d
 */

#include "LinkedListNode.h"
#include <iostream>
using namespace std;

void reverseLinkedListIterative(Node *&head){
	if(!head) return;
	Node *curr = head;
	Node *prev=NULL;
	while(curr){
		Node *tmp=curr->next;
		curr->next=prev;
		prev=curr;
		curr=tmp;
	}
	head=prev;
}

/*the rest pointer points to the last element and does not change
http://www.leetcode.com/2010/04/reversing-linked-list-iteratively-and.html*/
void reverseLinkedListRecursive(Node *&head){
	if(!head) return;
	Node *rest = head->next;
	if(!rest) return;
	reverseLinkedListRecursive(rest);
	head->next->next = head;
	head->next = NULL;
	head=rest;


}

/*http://www.leetcode.com/2010/09/splitting-linked-list.html*/
void split_linkedlist_in_half(Node *head, Node *first, Node *second){
	if(!head) return;
	Node *firstLast;
	Node *fast = head;
	Node *slow = head;

	while(fast){
		firstLast = slow;
		slow=slow->next;
		fast=(fast->next)?fast->next->next:NULL;
	}
	first = head;
	firstLast->next = NULL;
	second=slow;

}

/*
1) prev->val <= x <= current->val:
	Insert between prev and current.
2) x is the maximum or minimum value in the list:
	Insert before the head. (ie, the head has the smallest value and its prev->val > head->val.
3) Traverses back to the starting point:
	Insert before the starting point.*/
void insert_into_a_cyclic_sorted_list(Node *&head, int x){
	if(!head){
		head=new Node();
		head->data=x;
		head->next=head;
		return;
	}
	Node *prev = NULL;
	Node *curr=head;

	while(curr!=head){
		prev=curr;
		curr=curr->next;
		if(prev->data <= x && x <= curr->data) break; //case 1
		if(prev->data>curr->data&&(x<prev->data||x>curr->data)) break; //case2
	}
	Node *n=new Node();
	n->data = x;
	prev->next = n;
	n->next=curr;
}

///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
//        k         - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
Node* find_kth_node_to_tail(Node *head, int k){
	if(!head) return NULL;
	int i = 0;
	Node *n = head;
	while(i<k){
		if(!head) return NULL;
		else{
			head = head->next;
			i++;
		}
	}
	while(!head->next){
		head=head->next;
		n=n->next;
	}
	return n;
}

///////////////////////////////////////////////////////////////////////
// Delete a node in a list
// Input: pListHead - the head of list
//        pToBeDeleted - the node to be deleted
///////////////////////////////////////////////////////////////////////

void delete_a_node_in_a_list(Node *head, Node *del){
	if(!head||!del) return;

	if(del->next){
		del->data=del->next->data;
		del->next=del->next->next;
		delete del->next;
		del = NULL;
	}
	else{
		while(head->next!=del)
			head=head->next;
		head->next=NULL;
		delete del;
		del = NULL;
	}
}

///////////////////////////////////////////////////////////////////////
// Print a list from end to beginning
// Input: pListHead - the head of list
///////////////////////////////////////////////////////////////////////

void reverse_print(Node *head){
	if(head==NULL) return;

	reverse_print(head->next);
	cout<<head->data<< ' ';
}

/* find the first common node of 2 linked list */

int linkedlist_length(Node *head){
	if(head == NULL) return 0;
	int length = 0;
	while(head!=NULL){
		length++;
		head = head->next;
	}
	return length;
}

Node* first_common_node_in_2_linkedlist(Node *head1, Node *head2){

	if(head1 == NULL||head2==NULL)
		return NULL;

	int length1 = linkedlist_length(head1);
	int length2 = linkedlist_length(head2);

	Node *tmp1 = head1;
	Node *tmp2 = head2;

	if(length1 > length2)
		for(int i=0; i<length1-length2; i++)
			tmp1=tmp1->next;
	else if(length1 < length2)
		for(int i=0; i<length2-length2; i++)
			tmp2=tmp2->next;

	while(tmp1!=NULL && tmp2 != NULL && tmp1!=tmp2){
		tmp1 = tmp1->next;
		tmp2 = tmp2->next;
	}
	if(tmp1!=NULL && tmp2 !=NULL)
		return tmp1;
	else return NULL;
}

